1. Field of the Invention
The present invention relates generally to the field of reproducing images with limited tone reproduction capacity, where intermediate tones are represented by halftones, generally for computer graphics applications and the like. More particularly, the present invention relates to digital halftoning where a threshold array is used to control individual pixels in a halftone cell, and most particularly, to an implementation for halftoning using an overlapping threshold array such that the size of the threshold array is reduced.
2. Description of Related Art
When reproducing images in computer graphics, it is seldom possible to duplicate the values of the original scene. However, to create a believable image, a believable tonal representation is all that is required. The human eye and brain help by compensating for differences in illumination, tonal range and color surroundings. There exist two general categories of imaging systems, namely, those that reproduce acceptable tone directly and those that are not able to do so. The first category of imaging systems includes systems capable of rendering images having continuous tone. Among these are photography, television, and certain digital computer displays of sufficient tonal resolution. Such systems typically do not require halftones because the reproduction of tone depends on the linearity of the system, the limits with which it produces white and black, and the ambient light during viewing.
The second category of imaging systems includes systems with limited tone reproduction capacity. These are often binary devices, which can reproduce only two values corresponding to "on" and "off." In such binary systems, such as monochrome computer displays and commercial printing presses, intermediate tones must be represented by halftones. Such halftoning systems rely on the eye and brain to integrate numerous small features to achieve the impression of tone.
Halftoning is the process by which continuous-tone colors are approximated by a pattern of pixels that can achieve only a limited number of discrete colors. The most familiar case of this is the rendering of gray tones with black and white-pixels, as in a newspaper photograph. Generally, when halftoning is required, it occurs after all color components have been transformed by an appropriate transfer function.
A halftone pattern is made up of a region of pixels referred to as the halftone cell. The halftone cell contains a specific, repeatable pattern. The tonal resolution of a halftone pattern depends on the number of pixels in the halftone cell. Within any given halftone cell in an image, a certain percentage of the pixels may be "on" and the remaining pixels may be "off." The percentage of pixels that are on correspond to the tonal value that the cell represents. For example, if sixty percent of the pixels in a given cell are black and the rest are white, that cell emulates an ideal sixty percent gray tint.
At any given addressability (i.e., the number of pixels that can be addressed in an image), there is a trade-off between cell size and tonal resolution: the smaller the cell, the smaller the number of pixels it contains, and the fewer tonal values it can represent. Thus, for the best tonal resolution (i.e., the most gray levels), the halftone cell should be large so as to include as many pixels as possible. On the other hand, the bigger the cell, the more visible it becomes to the human eye, thereby sometimes distorting the picture. This tradeoff between gray levels and cell size is one of the classic problems of digital halftoning.
In conventional digital halftoning (using rational tangents), a threshold array is used to directly control the individual pixels in a halftone cell. A threshold array is much like a sampled image, because it is a rectangular array of pixel values. However, it is defined entirely in device space, and the sampled values typically occupy 8 bits each. Each pixel or element within the cell is assigned a threshold value, which represents the tonal value at which the pixel is turned on. The pixel values nominally represent gray levels, where the value 0 may be black and the value 255 may be white. When deciding whether to turn the pixel on, an imaging system checks the pixel's location in the halftone image, determines the tonal value of the image at that exact location, and compares this tonal value with the pixel's threshold value in the threshold array. If the tonal value exceeds the threshold value, the pixel is turned on when the image is created by the imaging system.
The threshold array is then replicated and tiled (i.e., filled) over the entire device space. Each pixel of device space is mapped to a particular element of the threshold array.
The threshold array defined in this way may contain data for one or multiple halftone cells. Moreover, the size of the threshold array can vary greatly. The reason for this is that a specific screen angle is implemented by tiling multiple halftone cells within the threshold array such that when the threshold array is tiled over a large area, it will produce the desired pattern of halftone cells. In other words, the threshold array must provide elements at its right edge that are in alignment with elements at its left edge such that when two threshold arrays are tiled by placing them adjacent to each other, the halftone cells between the arrays (over an edge of the threshold array) are identical to the cells within the array. Similarly, the same must be true in the vertical direction. For example, a 45 degree screen is implemented by tiling two halftone cells within the threshold array, as illustrated at 10 in FIG. 1A. By tiling the threshold array over a large area, a pattern of halftone cells is produced, as illustrated at 12 in FIG. 1B.
The size of the threshold array is directly determined by the rational tangent coefficients for the screen (i.e., the number of steps to the right and up in device space between one pixel in a halftone cell and the same pixel in a neighboring halftone cell). For example, a 45 degree screen with 600 dpi (dots per inch) and 106 lines, produced by replicating the halftone cell 4 steps to the right and 4 steps up, has 4, 4 as rational tangents coefficients. The size of the smallest threshold array (i.e., the size of the threshold array in pixels) required to correctly produce the halftone cell pattern, when tiled, is determined by the following equation: EQU n*A+m*B,
where A and B are the rational tangent coefficients and n and m are least common denominators such that: EQU n/m=A/B.
For the exemplary 45 degree screen with 106 lines, A=B=4 and n=m=1. The smallest threshold array required to produce the halftone screen has 8 by 8 elements (1*4+1*4=8). As shown in FIG. 1B, the threshold array size need only be 8 elements by 8 elements since at 45 degrees, the left and right edges match, as do the top and bottom edges. Therefore, the halftone cell 14 within the threshold array will be identical to the halftone cell 16 covering four threshold arrays.
One problem which surfaces with this method lies in the rapidly increasing size of the threshold array when n and m increase. This typically occurs in instances when the screen angle is small (i.e., close to 0 degrees), or when the screen angle is large (i.e., close to 90 degrees), or when the screen angle is a close approximation of an irrational tangent. This is especially important when the halftoning method is implemented in hardware, where the size of the threshold array directly translates to silicon area, and directly affects cost and manufacturability. In comparison, a screen with rational tangents of 4, 3 only requires 7 by 7 elements to create the halftone cell. However, the threshold array must be 25 by 25 elements such that the threshold array can be tiled with the right, left and top, bottom edges in alignment.
For example, a halftone screen with rational tangent coefficients of 4, 5 will require a 41 by 41 element threshold array, compared to the 8 by 8 element threshold array needed for the 45 degree halftone screen mentioned above. As another example, a 15 degree screen having 600 dpi and 106 lines may be approximated using a 2 by 2 super-cell with rational tangent coefficients of 11, 3. This generates a 105.25 line, 15.25 degree screen. The threshold array required to tile this super-cell has 130 by 130 elements (11*11+3*3=130), for a total storage size of 16,900 bytes.
Hence, because the size of a threshold array can grow drastically for small and large degree screens, large amounts of storage capacity are required in computer graphics systems where any degree screen may be specified. In smaller computer systems, a large storage capacity may be impractical. Additionally, large memory requirements dedicated to this purpose reduce available memory for other operations. Further, excessive memory results in additional cost and space considerations for hardware dedicated to halftoning. Thus, there is an ongoing need for an improved implementation of halftoning offering less expensive alternatives.